package woshiheima13;

import java.util.Arrays;

/**
 * 归并排序
 */
public class GuiBinSort {
    public static void main(String[] args) {
        int [] arr = new int []{1,7,3,5,2,4,6,8,10};
        System.out.println(Arrays.toString(arr));
       marge(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
//归并排序
    public static void marge(int[] arr,int low,int high){
        int middle = (low+high)/2;
        if (low<high){
            //左边的数组
            marge(arr,0,middle);
            //右边的数组
            marge(arr,middle+1,high);
            //执行操作把两个数组进行排序
            guiBingSort(arr,low,high,middle);
        }
    }

    public static void guiBingSort(int[] arr,int low,int high,int middle){
        //用于存储归并后的临时数组
        int [] temp = new int[high-low+1];
        //记录第一个数组中需要遍历的元素下标
        int i = low;
        //记录第二个数组中需要遍历的元素下标
        int j=middle+1;
        //用于存放临时数组的下标
        int index = 0;
        //遍历两个数组取出最小的数放入临时数组
        while (i<=middle&&j<high){
            if (arr[i]<=arr[j]){
                //把小的数放入临时数组中
                temp[index]=arr[i];
                //左边的指针+1
                i++;
            }else {
                temp[index]=arr[j];
                j++;
            }
            index++;
        }
        //把剩余的数组放入临时数组中
        //左边的数组还剩余的数放入临时数组
        while (i<=middle){
            temp[index]=arr[i];
            index++;
            i++;
        }
        //右边的数组还剩余的数放入临时数组
        while (j<=high){
            temp[index]=arr[j];
            index++;
            j++;
        }
        //把临时数组的数据放入原数组中
        for (int k=0;k<temp.length;k++){
            arr[k+low]=temp[k];
        }


    }
}
